package leetcode;

/**
 * 扁平化多级双向链表  
 */
public class LeetCode430 {
    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }


    public Node flatten(Node head) {
        if (head == null) return head;
        Node dummy = new Node();
        dummy.next = head;
        Node next = head.next;
        if (head.child != null) {
            head.next = flatten(head.child);
            head.next.prev = head;
            head.child = null;
            while (head.next != null) head = head.next;
        }
        if (next != null) {
            head.next = flatten(next);
            head.next.prev = head;
        }
        return dummy.next;
    }

}